
import array, getopt, sys, commands, string, tempfile, os, shutil, re, Image, ImageColor, ImageFilter, difflib

class RasterDiff:
	"""
		Allows line-by-line comparison (diff) of two raster images.

		Images are converted to single-bit (black&white) before conversion.
	"""

	def __init__(self, image_a, image_b):
		self.image_a = image_a.convert("1")
		self.image_b = image_b.convert("1")
		self.verbose = False
		self.show_horizontal_diff = True
		self.diff_ratio = None
		self.line_height = 0

		# colors for visual representation of changes
		self.deleted_text_color = ImageColor.getrgb( '#ffb7ba' ) # red
		self.added_text_color = ImageColor.getrgb( '#c1ffc1' )   # green
		self.vertical_change_color1 = ImageColor.getrgb( '#bcd2ee' )   # dark blue
		self.vertical_change_color2 = ImageColor.getrgb( '#ddeeff' )   # light blue
		self.horizontal_change_color1 = ImageColor.getrgb( '#ebdcee' )   # dark pink
		self.horizontal_change_color2 = ImageColor.getrgb( '#ffddfe' )   # light pink




	def compute_diff( self ):
		"""Computes the difference between the two images.
		   Returns a third image.
		"""

		self.image_a_chars = self.im2sequence( self.image_a )
		self.image_b_chars = self.im2sequence( self.image_b )

		sm = difflib.SequenceMatcher( self.isjunk )
		sm.set_seqs( self.image_a_chars, self.image_b_chars )

		self.diff_ratio = sm.ratio

		if self.verbose:
			print "diff ratio: " + str( sm.ratio() )

		slice_images = []


		index = 0
		n_ignored_slices = 0

		opcodes = sm.get_opcodes()
		for tag, i1, i2, j1, j2 in opcodes:

			if self.verbose and index % 100 == 0:
				print "concatenating slice " + str(index) + ' / ' + str( len( opcodes ) )

			w = self.image_a.size[0]
			h = 0

			slice_im = None


			if tag == "equal":
				h = i2 - i1
				slice_im = Image.new('RGBA', ( w, h) )
				slice_im.paste( self.image_a.crop( ( 0, i1, w, i2 ) ).convert("1") )

			elif tag == "delete":
				h = i2 - i1
				slice_im = Image.new('RGBA', ( w, h) )
				slice_im.paste( self.deleted_text_color, (0,0), self.image_a.crop( ( 0, i1, w, i2 ) ).convert("1") )

			elif tag == "insert":
				h = j2 - j1
				slice_im = Image.new('RGBA', ( w, h) )

				slice_im.paste( self.added_text_color, (0,0), self.image_b.crop( ( 0, j1, w, j2 ) ).convert("1") )

			elif tag == "replace":
				h = i2 - i1 + j2 - j1

				#print "slice " +str(index) + ", replace height: " + str(h)

				if h > self.line_height:
					slice_im = Image.new('RGBA', ( w, h) )

					new_color = self.vertical_change_color1
					old_color = self.vertical_change_color2

					# compute difference in new/old sections
					section_size_difference = abs ( (i2 - i1)  - ( j2 - j1 ) )

					if self.show_horizontal_diff and section_size_difference == 0:
						# the same (or nearly so)
						slice_im.paste( self.vertical_change_color1, (0,0), self.image_a.crop( (  0, i1, w, i2 ) ).convert("1") )
						slice_im.paste( self.vertical_change_color2, (0,i2-i1), self.image_b.crop( (  0, j1, w, j2 ) ).convert("1") )

						h_differences = self.compute_h_differences( self.image_a_chars[i1:i2], self.image_b_chars[j1:j2], w )


						for h in h_differences: 
							slice_im.paste( self.horizontal_change_color1, (h['x1'], 0), self.image_a.crop( (  h['x1'], i1, h['x2'], i2 ) ).convert("1") )
							slice_im.paste( self.horizontal_change_color2, (h['x1'], i2-i1), self.image_b.crop( (  h['x1'], j1, h['x2'], j2 ) ).convert("1") )

					else:
						slice_im.paste( self.vertical_change_color1, (0,0), self.image_a.crop( (  0, i1, w, i2 ) ).convert("1") )
						slice_im.paste( self.vertical_change_color2, (0,i2-i1), self.image_b.crop( (  0, j1, w, j2 ) ).convert("1") )

				else: 
					# assume slices below line_height are noise - treat as equal
					if self.verbose:
						print "ignoring slice of height " + str( h )
					n_ignored_slices += 1

					eh = i2 - i1
					slice_im = Image.new('RGBA', ( w, eh) )
					slice_im.paste( self.image_a.crop( ( 0, i1, w, i2 ) ).convert("1") )
			else:
				print "unknown slice tag: " + str(tag)
				exit(0)

			slice_images.append( slice_im )

			index += 1

			#if index > 50: break

		if self.verbose:
			print str( len( slice_images ) ) + ' diff slices'
			print str( n_ignored_slices ) + ' slices ignored (too small)'

		output_im = vcat_images( slice_images, 'RGBA' )

		return output_im


	def im2sequence( self, im ):
		""" transform a one-dimensional array of image data into a 2-dimensional array of "lines".
		"""

		im_data = list( im.getdata() )
		w = im.size[0]
		h = im.size[1]

		lines = []

		for i in range(h):
			lines.append( tuple( im_data[ i*w : i*w+w ] ) )   # convert to list
			if self.verbose and i % 1000 == 0:
				print "translating line " + str(i)

			#if i > 2000: break   # testing limit
			if i > 40000: break   # jpg size limit

		im_data = None

		return lines



	def isjunk( self, seq ):
		""" Simple heuristics to ignore noisy input
		"""
		#return False

		# ignore lines that are mostly white
		percent_white = float( sum( seq ) )  / float(  ( 255 * len( seq ) ) )
		#print "percent_white: " + str( percent_white )

		if percent_white > .95:
			return True

		# ignore lines that are mostly black
		if percent_white < .05:
			return True



		return False



	def compute_h_differences( self, a_data, b_data, w ):
		"""Given two same-length sequences data, returns a data structure describing the intervals where the data does not match.
		"""

		h_differences = []

		different_columns = []


		for i in range(w):
			v1 = [ j[i] for j in a_data ]
			v2 = [ j[i] for j in b_data ]
			if v1 != v2:
				different_columns.append(i)

		prev_i = None

		for i in different_columns:
			if i - 1 == prev_i:
				h_differences[-1]['x2'] = i
			else:
				h_differences.append( { 'x1' : i, 'x2' : i } )
			prev_i = i

		return h_differences


def vcat_images( images, mode ):
	h = sum(i.size[1] for i in images)
	mw = max(i.size[0] for i in images)

	result = Image.new( mode, (mw, h))

	y = 0
	for i in images:
		result.paste(i, (0, y))
		y += i.size[1]

	return result



